package demo1;

import java.util.*;

public class TreeNode {
        int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
     }
     //检验是否是相同二叉树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)return true;
        if(p==null||q==null)return false;
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //另一颗树的子树
    public boolean isSubtree1(TreeNode root, TreeNode subRoot) {
        if(subRoot==null)return true;
        if(root==null)return false;
        return isSubtree1(root.left,subRoot)||isSubtree1(root.right,subRoot)||isSame(root,subRoot);

    }
    public boolean isSame(TreeNode p,TreeNode q){
        if(p==null&&q==null)return true;
        if(p==null||q==null||p.val!=q.val)return false;
        return isSame(p.left,q.left)&&isSame(p.right,q.right);
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root==null)return null;
        TreeNode left=invertTree(root.left);
        TreeNode right=invertTree(root.right);
        root.left=right;
        root.right=left;
        return root;
    }
    //对称二叉树
//    public boolean isSymmetric(TreeNode root) {
//        if(root==null)return true;
//        TreeNode p=root.left;
//        TreeNode q=root.right;
//        return isSame(p,q);
//    }
//
//    public boolean isSame(TreeNode p,TreeNode q){
//        if(p==null&&q==null)return true;
//        if(p==null||q==null||p.val!=q.val)return false;
//        return isSame(p.left,q.right)&&isSame(p.right,q.left);
//    }
    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
          if(root==null)return true;
          int leftHight=getHeight(root.left);
          int rightHight=getHeight(root.right);
          return Math.abs(leftHight-rightHight)<=1 &&
                  isBalanced(root.left) && isBalanced(root.right);
    }
    int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }
    public boolean isBalanced2(TreeNode root) {
        return getHeight2(root)>=0;
    }
    int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int leftH = getHeight2(root.left);
        if(leftH<0){
            return -1;
        }
        int rightH = getHeight2(root.right);
        if(rightH>=0&&Math.abs(leftH - rightH) <= 1){
            return Math.max(leftH, rightH) + 1;
        }
        return -1;
    }
    //公共祖先
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p||root==q)return root;
        TreeNode lefttree=lowestCommonAncestor1(root.left,p,q);
        TreeNode righttree=lowestCommonAncestor1(root.right,p,q);
        if(lefttree!=null&&righttree!=null){
            return root;
        }else if(lefttree!=null){
            return lefttree;
        }else{
            return righttree;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> s1=new Stack<>();
        Stack<TreeNode> s2=new Stack<>();
        getPath(root,p,s1);
        getPath(root,q,s2);
        if(s1.size()>s2.size()){
            int len=s1.size()-s2.size();
            while(len!=0){
                s1.pop();
                len--;
            }
        }else{
            int len=s2.size()-s1.size();
            while(len!=0){
                s2.pop();
                len--;
            }
        }
        while(!s1.isEmpty()&&!s2.isEmpty()){
            if(s1.peek()==s2.peek()){
                return s1.peek();
            }else{
                s1.pop();
                s2.pop();
            }
        }
        return null;
    }
    public boolean getPath(TreeNode root,TreeNode target,Stack<TreeNode> stack){
        if(root==null) return false;
        stack.push(root);
        if(root==target) return true;
        if(getPath(root.left,target,stack)){
            return true;
        }
        if(getPath(root.right,target,stack)){
            return true;
        }stack.pop();
        return false;
    }
    //非递归实现二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
          List<Integer> list=new ArrayList<>();
          if(root==null)return list;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode node=root;
        while(node!=null||!stack.isEmpty()) {
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }
    //非递归实现中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> list=new ArrayList<>();
          if(root==null) return list;
          Stack<TreeNode> stack=new Stack<>();
          TreeNode node=root;
          while(node!=null||!stack.isEmpty()) {
              while (node != null) {
                  stack.push(node);
                  node = node.left;
              }
              node = stack.pop();
              list.add(node.val);
              node = node.right;
          }
          return list;
    }
    //非递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root=stack.pop();
            if(root.right==null||root.right==node){
                list.add(root.val);
                node=root;
                root=null;
            }else{
                stack.push(root);
                root=root.right;
            }

        }
        return list;
    }
}
